//给定一个包含红色、白色和蓝色、共 n 个元素的数组
// nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
//
// 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
//
//
//
//
// 必须在不使用库内置的 sort 函数的情况下解决这个问题。
//
//
//
// 示例 1：
//
//
//输入：nums = [2,0,2,1,1,0]
//输出：[0,0,1,1,2,2]
//
//
// 示例 2：
//
//
//输入：nums = [2,0,1]
//输出：[0,1,2]
//
//
//
//
// 提示：
//
//
// n == nums.length
// 1 <= n <= 300
// nums[i] 为 0、1 或 2
//
//
//
//
// 进阶：
//
//
// 你能想出一个仅使用常数空间的一趟扫描算法吗？
//
//
// Related Topics 数组与矩阵 双指针 排序 👍 1576 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 Do not return anything, modify nums in-place instead.
 */
function sortColors(nums: number[]): void {
    /*
    双指针，当前值为 2，那么就和右边指针进行交换，反之当前值为 0，那么就和左边指针进行交换，为 1 就不动。
     */
    let len = nums.length;
    let L = 0;
    let R = len - 1;
    let i = 0;
    while (i <= R) {
        if (nums[i] == 0) {
            // 当前值为0，那么就和左边指针进行交换
            [nums[i], nums[L]] = [nums[L], nums[i]];
            L++;
            // 此时i可以加 因为前面的都是小的
            i++;
        } else if (nums[i] == 2) {
            // 当前值为2，那么就和右边指针进行交换
            [nums[i], nums[R]] = [nums[R], nums[i]];
            // 这里不加i 是因为有可能换个大的来
            R--;
        } else {
            i++;
        }
    }
};
//leetcode submit region end(Prohibit modification and deletion)
